package _08_堆;

import _05_树.printer.BinaryTrees;
import org.junit.Test;

import java.util.Comparator;

public class HeapTest {
    @Test
    public void testHeap(){
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(10);
        heap.add(90);
        heap.add(65);
        BinaryTrees.println(heap);
        heap.remove();
        BinaryTrees.println(heap);
        System.out.println(heap.replace(20));
        BinaryTrees.println(heap);
    }

    @Test
    public void testHeapify(){
        Integer[] data = {25,68,45,12,36,98,77,66,52,14,86};
        BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //根据返回结果，大于0的，左边大，小于0的，右边大
                // o1 20 o2 10  o1 - o2 = 10 o1大
                // o1 10 o2 20 o1 - o2 = -10 右边大
                //return o1 - o2;
                return o2 - o1;
            }
        });
        BinaryTrees.println(heap);
    }

    //TopK问题，使用小顶堆
    //从n个整数中，找出最大的前k个数(k远远小于n)
    @Test
    public void topK(){
        Integer[] data = {88, 55, 73, 3, 41, 29, 67, 80, 100, 97, 54, 1, 12, 21, 25, 99, 62, 98, 23, 19, 26, 24, 50, 90, 72};
        //新建一个小顶堆
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //根据返回结果，大于0的，左边大，小于0的，右边大
                // o1 20 o2 10  o1 - o2 = 10 o1大
                // o1 10 o2 20 o1 - o2 = -10 右边大
                //return o1 - o2;
                return o2 - o1;
            }
        });
        int k = 3; //找出最大的前三个数
        //遍历n个数
        for(int i=0;i<data.length;++i){
            if(heap.size<k){
                heap.add(data[i]); //将前k个数放入小顶堆
            }else if(data[i]>heap.get()){ //从第k+1个数开始，只要大于堆顶元素，就将堆顶元素删除，并添加到堆顶元素，进行下滤
                heap.replace(data[i]); //这样删除的都是最小的元素，留下的都是最大的
            }
        }
        BinaryTrees.println(heap);


    }

    @Test
    public void testB(){
        Integer[] array = {3,2,1,5};
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (Integer integer : array) {
            heap.add(integer);
        }
        BinaryTrees.println(heap);
    }

}
